package com.study.homework;

import com.study.bniarysearch.BinarySearch;
import com.study.sort.QuickSort;
import com.study.sort.SortMain;

/**
 * 关于散列表和字符串的 4 个必知必会的代码实现
 * 散列表
 * 实现一个基于链表法解决冲突问题的散列表
 * 实现一个 LRU 缓存淘汰算法
 * 字符串
 * 实现一个字符集，只包含 a～z 这 26 个英文字母的 Trie 树
 * 实现朴素的字符串匹配算法
 * <p>
 * 对应的LeetCode 练习题（@Smallfly 整理）
 * 字符串Reverse String （反转字符串）
 * 英文版：https://leetcode.com/problems/reverse-string/
 * 中文版：https://leetcode-cn.com/problems/reverse-string/
 * Reverse Words in a String（翻转字符串里的单词）
 * 英文版：https://leetcode.com/problems/reverse-words-in-a-string/
 * 中文版：https://leetcode-cn.com/problems/reverse-words-in-a-string/
 * String to Integer (atoi)（字符串转换整数 (atoi)）
 * 英文版：https://leetcode.com/problems/string-to-integer-atoi/
 * 中文版：https://leetcode-cn.com/problems/string-to-integer-atoi/
 */
public class Day4 {
    public static void main(String[] args) {
        //实现一个基于链表法解决冲突问题的散列表
//        MyHashSet hashSet = new MyHashSet();
//        for (int i = 0; i < 30; i++) {
//            hashSet.put(i);
//        }
//        for
// (int i = 20; i < 40; i++) {
//            System.out.println(i + " : " + hashSet.get(i));
//        }
        //量化 散列表 与 二分法的 速度差距
//        showSearch();

        // 实现一个 LRU 缓存淘汰算法
        MyLru lru = new MyLru(3);
        lru.put(1);
        lru.put(3);
        lru.put(5);
        lru.put(1);
        lru.put(2);
        lru.put(5);
        System.out.println(lru.toString());



    }

    private static void showSearch() {
        //量化 散列表 与 二分法的 速度差距
        //
        //   三个数量级 有序数组
        // 散列表 数组1024,

        QuickSort quickSort = new QuickSort();

        int[] a = quickSort.run(SortMain.getInts(100, 100));
        int[] b = quickSort.run(SortMain.getInts(1000, 10000));
        int[] c = quickSort.run(SortMain.getInts(1000000, 10000000));

        round(1, a);
        round(2, b);
        round(3, c);

        /*
        100  1000  1000000  三个数量级 有序数组
        hash成绩包含了 array转存hashSet的时间,成绩如下:

        第1回合 hash成绩:		        90200
        第1回合 BSearch(递归)成绩:		2387400
        第1回合 BSearch(循环)成绩:		126800
        ----------------------------
        第2回合 hash成绩:		        5085900
        第2回合 BSearch(递归)成绩:		8152200
        第2回合 BSearch(循环)成绩:		6463800
        ----------------------------
        第3回合 hash成绩:		        124470447900
        第3回合 BSearch(递归)成绩:		6336514600
        第3回合 BSearch(循环)成绩:		6281768700

        总结
        第一组长度100,远小于hash内部数组长度,hash碰撞率很低,效率也很优秀
        第二组长度1000,基本等于长度hash长度,存在一定hash碰撞率(所以hashMap的扩容因子为0.75),总体也比二分法成绩良好
        第三组长度1000000, 远超hash内部数组长度,大量hash碰撞,使得hashSet降维成了单项链表,导致成绩比二分法差很多
        二分法的递归与循环两种实现,总体差别不大,差亦可能是我的算法写的不好..
         */
    }

    private static void round(int num, int[] a) {
        //回合.
        long start = System.nanoTime();
        MyHashSet hashSet = new MyHashSet();
        for (int i : a) {
            hashSet.put(i);
        }

        for (int i = 0; i < a.length; i++) {
            hashSet.get(i);
        }
        System.out.println("第" + num + "回合 hash成绩:\t\t" + (System.nanoTime() - start));

        start = System.nanoTime();
        for (int i = 0; i < a.length * 10; i++) {
            BinarySearch.bSearch(a, i, 0, a.length - 1);
        }
        System.out.println("第" + num + "回合 BSearch(递归)成绩:\t\t" + (System.nanoTime() - start));

        start = System.nanoTime();
        for (int i = 0; i < a.length * 10; i++) {
            BinarySearch.bSearch(a, i, 0, a.length - 1);
        }
        System.out.println("第" + num + "回合 BSearch(循环)成绩:\t\t" + (System.nanoTime() - start));
    }


}
